On the word, subsumption, and complement problem for recurrent term schematizations
Identifieur interne : 00B336 ( Main/Exploration ); précédent : 00B335; suivant : 00B337On the word, subsumption, and complement problem for recurrent term schematizations
Auteurs : Miki Hermann [France] ; Gernot Salzer [Autriche]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Descripteurs français
- Pascal (Inist)
English descriptors
Abstract
Abstract: We investigate the word and the subsumption problem for recurrent term schematizations, which are a special type of constraints based on iteration. By means of unification, we reduce these problems to a fragment of Presburger arithmetic. Our approach is applicable to all recurrent term schematizations having a finitary unification algorithm. Furthermore, we study a particular form of the complement problem. Given a finite set of terms, we ask whether its complement can be finitely represented by schematizations, using only the equality predicate without negation. The answer is negative as there are ground terms too complex to be represented by schematizations with limited resources.
Url:
DOI: 10.1007/BFb0055775
Affiliations:
- Autriche, France
- Grand Est, Lorraine (région), Vienne (Autriche)
- Vandœuvre-lès-Nancy, Vienne (Autriche)
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 003B54
- to stream Istex, to step Curation: 003B10
- to stream Istex, to step Checkpoint: 002568
- to stream Main, to step Merge: 00BA58
- to stream PascalFrancis, to step Corpus: 000B94
- to stream PascalFrancis, to step Curation: 000C80
- to stream PascalFrancis, to step Checkpoint: 000B38
- to stream Main, to step Merge: 00BB60
- to stream Main, to step Curation: 00B336
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the word, subsumption, and complement problem for recurrent term schematizations</title><author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name></author><author><name sortKey="Salzer, Gernot" sort="Salzer, Gernot" uniqKey="Salzer G" first="Gernot" last="Salzer">Gernot Salzer</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:F885D4F58E39DC7DF11A92FBA818614389D64AD3</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1007/BFb0055775</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-PNGN4MVL-8/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003B54</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003B54</idno><idno type="wicri:Area/Istex/Curation">003B10</idno><idno type="wicri:Area/Istex/Checkpoint">002568</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002568</idno><idno type="wicri:doubleKey">0302-9743:1998:Hermann M:on:the:word</idno><idno type="wicri:Area/Main/Merge">00BA58</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:98-0425359</idno><idno type="wicri:Area/PascalFrancis/Corpus">000B94</idno><idno type="wicri:Area/PascalFrancis/Curation">000C80</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000B38</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B38</idno><idno type="wicri:doubleKey">0302-9743:1998:Hermann M:on:the:word</idno><idno type="wicri:Area/Main/Merge">00BB60</idno><idno type="wicri:Area/Main/Curation">00B336</idno><idno type="wicri:Area/Main/Exploration">00B336</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the word, subsumption, and complement problem for recurrent term schematizations</title><author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA (CNRS), BP 239, 54506, Vandœuvre-lès-Nancy</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Salzer, Gernot" sort="Salzer, Gernot" uniqKey="Salzer G" first="Gernot" last="Salzer">Gernot Salzer</name><affiliation wicri:level="3"><country xml:lang="fr">Autriche</country><wicri:regionArea>Technische Universität Wien, Karlsplatz 13, 1040, Wien</wicri:regionArea><placeName><settlement type="city">Vienne (Autriche)</settlement><region nuts="2" type="province">Vienne (Autriche)</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Autriche</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><title level="s" type="abbrev">Lect Notes Comput Sci</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computer theory</term><term>Language theory</term><term>Rewriting systems</term><term>Semantic analysis</term><term>Syntactic analysis</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Analyse syntaxique</term><term>Analyse sémantique</term><term>Informatique théorique</term><term>Système réécriture</term><term>Théorie langage</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We investigate the word and the subsumption problem for recurrent term schematizations, which are a special type of constraints based on iteration. By means of unification, we reduce these problems to a fragment of Presburger arithmetic. Our approach is applicable to all recurrent term schematizations having a finitary unification algorithm. Furthermore, we study a particular form of the complement problem. Given a finite set of terms, we ask whether its complement can be finitely represented by schematizations, using only the equality predicate without negation. The answer is negative as there are ground terms too complex to be represented by schematizations with limited resources.</div></front></TEI><affiliations><list><country><li>Autriche</li><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Vienne (Autriche)</li></region><settlement><li>Vandœuvre-lès-Nancy</li><li>Vienne (Autriche)</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name></region><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name></country><country name="Autriche"><region name="Vienne (Autriche)"><name sortKey="Salzer, Gernot" sort="Salzer, Gernot" uniqKey="Salzer G" first="Gernot" last="Salzer">Gernot Salzer</name></region><name sortKey="Salzer, Gernot" sort="Salzer, Gernot" uniqKey="Salzer G" first="Gernot" last="Salzer">Gernot Salzer</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B336 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B336 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:F885D4F58E39DC7DF11A92FBA818614389D64AD3
|texte= On the word, subsumption, and complement problem for recurrent term schematizations
}}
| This area was generated with Dilib version V0.6.33. |  |